package com.zhang.eightSorts;

import java.time.LocalDateTime;
import java.util.Arrays;

/**
 * 插入排序
 * 循环判断【前面】的数是否大于自己。
 *
 */
public class InsertSort {

    /**
     * 插入排序单次
     * @param a
     */
    InsertSort(int[] a)
    {
        int insertVal =0;
        int insertindex = 0;
        for(int i=1;i<a.length;i++) {
//        new  int[]{101,34,119,1;
            //数组从第二个也就是下表为1的位置开始走，循环判断前面的数是否大于自己。

            insertVal=a[i];
            insertindex=i - 1;
            //使用下面方式执行互换
            while (insertindex >= 0 && insertVal < a[insertindex]) {//如果下标存在，并且当前值小于于前一位值则互换位置。
                a[insertindex + 1] = a[insertindex];
                insertindex--;

            }
            if (insertindex+1==i) {
                a[insertindex + 1] = insertVal;
            }
  }
    }
}
class Tests {
 public    static void main(String[] arg0) {

     int[] arr=new int[80000];
     for (int i=0;i<arr.length;i++)
     {
         arr[i]=(int)(Math.random()*8000000);
     }
     int[] a=new  int[]{101,34,119,1};
     System.out.println(LocalDateTime.now());
     new InsertSort(arr);
     System.out.println(LocalDateTime.now());

 }
}
